<!doctype html><html lang=cn-zh><head><meta charset=UTF-8><meta name=viewport content="width=device-width,initial-scale=1"><meta http-equiv=X-UA-Compatible content="IE=edge"><style type=text/css>body{font-family:monospace}</style><title>[算法笔记]用递归和迭代的思想分别实现插入排序和选择排序</title>
<meta name=description content="A blog maintained by Vimiix."><link rel=stylesheet href=/css/style.css><script>var _hmt=_hmt||[];(function(){var e,t=document.createElement("script");t.src="https://hm.baidu.com/hm.js?7c24231917964240bae97e813810620c",e=document.getElementsByTagName("script")[0],e.parentNode.insertBefore(t,e)})()</script></head><body><header>====================<br>== Hi, I'm Vimiix ==<br>====================<div style=float:right;color:gray;font-size:x-large>Get hands dirty.</div><br><p><nav><a href=https://www.vimiix.com/><b>首页</b></a>.
<a href=/posts/><b>文章列表</b></a>.
<a href=/projects/><b>开源项目</b></a>.
<a href=/tags/><b>标签</b></a>.
<a href=/friends/><b>友链</b></a>.
<a href=/about/><b>关于我</b></a>.
<a href=/index.xml><b>RSS</b></a>.</nav></p></header><main><article><h1>[算法笔记]用递归和迭代的思想分别实现插入排序和选择排序</h1><b><time>2017.08.02 17:17</time></b>
<a href=/tags/python>python</a>
<a href=/tags/algorithms>algorithms</a><div><h1 id=思路>思路</h1><h3 id=插入排序insert-sort>插入排序（insert sort）</h3><blockquote><p>先归纳性的假设前 n-1 个元素已经完成排序了，现在要将第 n 个元素向前插入到正确的位置上。这种方式称之为<strong>插入排序法</strong></p></blockquote><h3 id=选择排序selection-sort>选择排序（selection sort）</h3><blockquote><p>先找到整个序列中最大的元素，并将其向后放在 n（待排序的序列末尾）的位置上，然后继续递归排序剩下的元素。这种方式称之为<strong>选择排序法</strong></p></blockquote><h1 id=python-代码实现>Python 代码实现</h1><h3 id=递归版插入排序>递归版插入排序</h3><div class=highlight><pre tabindex=0 style=color:#f8f8f2;background-color:#272822;-moz-tab-size:4;-o-tab-size:4;tab-size:4><code class=language-Python data-lang=Python><span style=display:flex><span>
</span></span><span style=display:flex><span>	<span style=color:#66d9ef>def</span> <span style=color:#a6e22e>ins_sort_rec</span>(seq, i):
</span></span><span style=display:flex><span>	  <span style=color:#66d9ef>if</span> i <span style=color:#f92672>==</span> <span style=color:#ae81ff>0</span>:                                  <span style=color:#75715e>#单元素情况，直接返回</span>
</span></span><span style=display:flex><span>	    <span style=color:#66d9ef>return</span>
</span></span><span style=display:flex><span>	  ins_sort_rec(seq, i<span style=color:#f92672>-</span><span style=color:#ae81ff>1</span>)                      <span style=color:#75715e>#递归排序0~(i-1)的元素，排好后，后面会将i的元素向前插入</span>
</span></span><span style=display:flex><span>	  j <span style=color:#f92672>=</span> i
</span></span><span style=display:flex><span>	  <span style=color:#66d9ef>while</span> j <span style=color:#f92672>&gt;</span> <span style=color:#ae81ff>0</span> <span style=color:#f92672>and</span> seq[j<span style=color:#f92672>-</span><span style=color:#ae81ff>1</span>] <span style=color:#f92672>&gt;</span> seq[j]:          <span style=color:#75715e>#寻找合适的位置，直到找到比seq[j]小的元素时，停止循环</span>
</span></span><span style=display:flex><span>	    seq[j<span style=color:#f92672>-</span><span style=color:#ae81ff>1</span>], seq[j] <span style=color:#f92672>=</span> seq[j], seq[j<span style=color:#f92672>-</span><span style=color:#ae81ff>1</span>]       <span style=color:#75715e>#交换位置</span>
</span></span><span style=display:flex><span>	    j <span style=color:#f92672>-=</span> <span style=color:#ae81ff>1</span>                                    <span style=color:#75715e>#递减索引值</span>
</span></span></code></pre></div><p>这段代码概括了该算法的思路：如果想要对目标序列中的第 i 个元素进行排序，首先要对 i-1 个元素进行递归性排序，并通过交换方式将<code>seq[i]</code>放到其已排序元素中的正确位置上，。尽管这种实现形式可以让我们在递归调用中很好的概括其归纳前提，但在具体实践中会受到限制（<em>例如：它只能在一定的序列长度下正常工作</em>）。</p><h3 id=迭代版插入排序>迭代版插入排序</h3><div class=highlight><pre tabindex=0 style=color:#f8f8f2;background-color:#272822;-moz-tab-size:4;-o-tab-size:4;tab-size:4><code class=language-Python data-lang=Python><span style=display:flex><span>
</span></span><span style=display:flex><span>	<span style=color:#66d9ef>def</span> <span style=color:#a6e22e>ins_sort</span>(seq):
</span></span><span style=display:flex><span>	  <span style=color:#66d9ef>for</span> i <span style=color:#f92672>in</span> range(<span style=color:#ae81ff>1</span>,len(seq)):                  <span style=color:#75715e>#从0到(i-1)排序</span>
</span></span><span style=display:flex><span>	    j <span style=color:#f92672>=</span> i                                      <span style=color:#75715e>#j作为扫描索引从后向前扫描，i为每一次的要插入的序列长度</span>
</span></span><span style=display:flex><span>	    <span style=color:#66d9ef>while</span> j <span style=color:#f92672>&gt;</span> <span style=color:#ae81ff>0</span> <span style=color:#f92672>and</span> seq[j<span style=color:#f92672>-</span><span style=color:#ae81ff>1</span>] <span style=color:#f92672>&gt;</span> seq[j]:         <span style=color:#75715e>#寻找合适位置</span>
</span></span><span style=display:flex><span>	      seq[j<span style=color:#f92672>-</span><span style=color:#ae81ff>1</span>], seq[j] <span style=color:#f92672>=</span> seq[j], seq[j<span style=color:#f92672>-</span><span style=color:#ae81ff>1</span>]      <span style=color:#75715e>#依次交换位置</span>
</span></span><span style=display:flex><span>	      j <span style=color:#f92672>-=</span> <span style=color:#ae81ff>1</span>                                   <span style=color:#75715e>#递减索引值扫描</span>
</span></span></code></pre></div><p>上面这段代码所展示的则是更为人们所熟知的迭代版插入排序。它将原先的后退式递归调用改成了从第一个元素开始的前进式迭代操作。但仔细推敲一下，就会发现递归也是这样做的。尽管看起来递归似乎是从序列尾端开始的，但是 while 循环被执行之前，这些递归调用得要先完全回退到第一个元素上。然后在该递归调用开始返回之后，while 循环才能开始处理第二个元素，并以此类推下去。所以，以上两个版本的行为其实是相同的。</p><h3 id=递归版选择排序>递归版选择排序</h3><div class=highlight><pre tabindex=0 style=color:#f8f8f2;background-color:#272822;-moz-tab-size:4;-o-tab-size:4;tab-size:4><code class=language-Python data-lang=Python><span style=display:flex><span>
</span></span><span style=display:flex><span>	<span style=color:#66d9ef>def</span> <span style=color:#a6e22e>sel_sort_rec</span>(seq, i):
</span></span><span style=display:flex><span>	  <span style=color:#66d9ef>if</span> i <span style=color:#f92672>==</span> <span style=color:#ae81ff>0</span>:                                   <span style=color:#75715e>#单元素直接返回</span>
</span></span><span style=display:flex><span>	    <span style=color:#66d9ef>return</span>
</span></span><span style=display:flex><span>	  max_j <span style=color:#f92672>=</span> i                                    <span style=color:#75715e>#初始化一个max_j作为要找的最大元素的索引值，先假设目前序列的最后一个为最大值</span>
</span></span><span style=display:flex><span>	  <span style=color:#66d9ef>for</span> j <span style=color:#f92672>in</span> range(i):                           <span style=color:#75715e>#寻找最大元素</span>
</span></span><span style=display:flex><span>	    <span style=color:#66d9ef>if</span> seq[j] <span style=color:#f92672>&gt;</span> seq[max_j]:
</span></span><span style=display:flex><span>	      max_j <span style=color:#f92672>=</span> j                                <span style=color:#75715e>#找到一个比seq[i]大的就更新max_j的值</span>
</span></span><span style=display:flex><span>	  seq[i], seq[max_j] <span style=color:#f92672>=</span> seq[max_j], seq[i]      <span style=color:#75715e>#将最大的元素放到末尾</span>
</span></span><span style=display:flex><span>	  sel_sort_rec(seq, i<span style=color:#f92672>-</span><span style=color:#ae81ff>1</span>)                       <span style=color:#75715e>#继续排列前i-1个元素</span>
</span></span></code></pre></div><h3 id=迭代版选择排序>迭代版选择排序</h3><div class=highlight><pre tabindex=0 style=color:#f8f8f2;background-color:#272822;-moz-tab-size:4;-o-tab-size:4;tab-size:4><code class=language-Python data-lang=Python><span style=display:flex><span>
</span></span><span style=display:flex><span>	<span style=color:#66d9ef>def</span> <span style=color:#a6e22e>sel_sort</span>(seq):
</span></span><span style=display:flex><span>	  <span style=color:#66d9ef>for</span> i <span style=color:#f92672>in</span> range(len(seq)<span style=color:#f92672>-</span><span style=color:#ae81ff>1</span>, <span style=color:#ae81ff>0</span>, <span style=color:#f92672>-</span><span style=color:#ae81ff>1</span>):           <span style=color:#75715e>#从最长开始依次递减将最大元素放在末尾</span>
</span></span><span style=display:flex><span>	    max_j <span style=color:#f92672>=</span> i                                  <span style=color:#75715e>#初始化max_j的索引值</span>
</span></span><span style=display:flex><span>	    <span style=color:#66d9ef>for</span> j <span style=color:#f92672>in</span> range(i):                         <span style=color:#75715e>#寻找最大值</span>
</span></span><span style=display:flex><span>		  <span style=color:#66d9ef>if</span> seq[j] <span style=color:#f92672>&gt;</span> seq[max_j]:
</span></span><span style=display:flex><span>	        max_j <span style=color:#f92672>=</span> j                              <span style=color:#75715e>#更新最大元素的索引值</span>
</span></span><span style=display:flex><span>	    seq[i], seq[max_j] <span style=color:#f92672>=</span> seq[max_j], seq[i]    <span style=color:#75715e>#奖最大元素后放</span>
</span></span></code></pre></div><p>这两段代码和上面一样，递归版实现明确表示了其归纳前提，而迭代版则明确说明了其反复迭代执行的归纳步骤。两者都是先找出最大元素，并将其交换到当前所关注序列的尾端。</p></div></article></main><aside><div><div><h3>LATEST POSTS</h3></div><div><ul><li><a href=/posts/2025-10-16-kubernetes-apiserver-authorization-mechanism/>Kubernetes APIServer 鉴权机制</a></li><li><a href=/posts/2025-09-30-kubernetes-apiserver-authentication-mechanism/>Kubernetes APIServer 认证机制</a></li><li><a href=/posts/2024-12-16-deploy-kubernetes-by-kubeadm/>使用 kubeadm 搭建 kubernetes 集群</a></li><li><a href=/posts/2024-09-20-how-to-code-review/>如何做code review</a></li><li><a href=/posts/2024-08-12-weakref-in-python/>Python中的弱引用</a></li></ul></div></div></aside><footer><p>Social Links:
<a href=https://github.com/vimiix><b>Github</b></a>.
<a href=https://www.douban.com/people/vimiix/><b>Douban</b></a>.
<a href=mailto:i@vimiix.com><b>Email</b></a>.<br><hr>&copy; 2017-2025
Vimiix Yao; All rights reserved.
<a href=https://beian.miit.gov.cn/>京ICP备19015214号-1</a></p><script src=https://l2dwidget.js.org/lib/L2Dwidget.min.js></script><script>L2Dwidget.init({model:{jsonPath:"https://unpkg.com/live2d-widget-model-tororo@1.0.5/assets/tororo.model.json"}})</script></footer></body></html>